

import Foundation

public class ListNode {
     public var val: Int
     public var next: ListNode?
     public init(_ val: Int) {
         self.val = val
         self.next = nil
     }
 }

func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    var list1 = l1;
    var list2 = l2;
    var pre : ListNode?;

    let preHead = ListNode(0);
    pre = preHead;

    while (list1 != nil && list2 != nil){
        if((list1?.val)! < (list2?.val)!){
            pre?.next = list1;
            list1 = list1?.next;
        }
        else{
            pre?.next = list2;
            list2 = list2?.next;
        }
        pre = pre?.next;
    }
    pre?.next = list1 ?? list2;
    return preHead.next;
}
